typedef struct n{
				 int clef,info,rouge;
				 struct n *g,*d;
	             }noeud;
				 
noeud *r,*cour,*p,*gp,*agp;


void initialisation()
{
/*initialisation*/
  r=(noeud*)malloc(sizeof(noeud));
  r->clef=-1;/*plus petite de toutes les clefs*/
  r->d=r->g=NULL;
}

void insertion(int clef,int info)
{
cour=p=gp=agp=r;
while(cour!=NULL){
gp=p;p=cour;
cour=(clef < cour->clef)?cour->g:cour->d;
if(cour->g->rouge && cour->d->rouge)
     eclater(clef);
	 }

cour=(noeud*)malloc(sizeof(noeud));
 cour->clef=clef;
 cour->info=info;
 cour->d=cour->g=NULL;
 if(clef < p->clef) p->g=cour;
 else p->d=cour;
eclater(clef); 
 }
 
 
void eclater(int clef)
{
cour->rouge=1;
cour->g->rouge=cour->d->rouge=0;
if(p->rouge){
gp->rouge=1;
if(clef < gp->clef!= clef < p->clef)
   p=rotation(clef,gp);
cour=rotation(clef,agp);
cour->rouge=0;
}
r->d->rouge=0;
}



 noeud *rotation(int clef,noeud *y)
{
c=(clef < y->clef) ? y->g : y->d;
if(clef < c->clef){
 gc=c->g;c->g=gc->d;gc->d=c;}
else{
 gc=c->d;c->d=gc->g;gc->g=c;}

if(clef < y->clef) y->g=gc;
else y->d=gc;
return(gc);
}



